Corelab Seminar
2012-2013
Ioannis Papoutsakis (University of Toronto)
Tree Spanners of small diameter
Abstract.
A tree t-spanner of a graph is a subtree of the graph such that for each
pair of vertices their distance in the tree is at most t times their
distance
in the graph. Such a problem is NP complete for t>3 and tractable for
t<3; while the situation for t=3 is unresolved.
If a graph admits a spanning tree of diameter at most t, then it trivially
admits a tree t-spanner as well. In this talk we move one step away form
the trivial case and for each t we examine the problem of whether a graph
admits a tree t-spanner of diameter at most t+1. It is shown that such a
problem is NP complete for t>3 and its efficiently solvable for t<4.